package demo.DataStrucAndAlgo.Tree.AVL;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/6-08-06-16:34
 * @Description：demo.DataStrucAndAlgo.Tree.AVL    AVL平衡二叉树
 */
/*
AVL树（平衡二叉树）
   AVL树是BST树的升级版。在旋转前，应该先要知道左右树的高度差是多少，有没有超过1。
   所以在BST树的Node类中追加 height，leftHeight，rightHeight方法，用于获取当前结点为父节点的子树高度
   ，左子树的高度，右子树的高度。
 */
class Node{
    private int data;
    private Node left;
    private Node right;

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public Node() {
    }

    public Node(int data) {
        this.data = data;
    }

    /**
     * 通过递归获得二叉树的高度
     * @return   二叉树的高度
     */
    public int height(){
        //通过递归左右结点，为空时停止递归，否则继续递归，每轮递归高度加1，递归完成选取大的作为高度
        return Math.max(left==null?0:left.height(),right==null?0: right.height())+1;
    }

    /**
     * 返回当前结点的左子树高度
     * @return    左子树高度
     */
    public int leftHeight(){
        if(left==null){
            return 0;
        }
        return left.height();
    }

    /**
     * 返回当前结点的右子树高度
     * @return   右子树高度
     */
    public int rightHeight(){
        if(right == null){
            return 0;
        }
        return this.right.height();
    }

    /** 当右子树高度-左子树高度>1 时，开始左旋：
            复制出一个与当前结点一样的结点
            将新结点的左子树与当前结点的左子节点相连，将当前结点的右子节点的左子结点与新结点的右结点相连
            将当前结点的右子节点的值,赋给当前结点，并将当前结点的右节点与右子节点的右子节点相连
            将当前结点的左节点与新结点相连
     * 对当前结点进行左旋平衡操作
     */
    public void leftRotate(){
        //1、复制出一个与当前结点一样的结点
        Node newNode = new Node(this.data);
        //2、将新节点的左子树与当前结点的左子树结点相连，将当前结点的右子树结点的左子树结点与新结点的右节点相连
        newNode.setLeft(this.left);
        newNode.setRight(this.right.left);
        //3、将当前结点的右子树节点的值赋给当前结点，并将当前结点的右子树节点与右子节点的右子树结点相连
        this.data = this.right.data;
        this.right = this.right.right;
        //4、将当前结点的左子树结点与新节点相连
        this.left = newNode;
    }

    /**
     * 对当前结点进行右旋平衡操作
     * ，当左子树高度-右子树高度>1 时，开始右旋：
     *       复制出一个与当前结点一样的结点
     *       将新结点的右节点与当前结点的右子节点相连，将当前结点的左子节点的右子结点与新结点的左结点相连
     *       将当前结点的左子节点的值,赋给当前结点，并将当前结点的左节点与左子节点的左子节点相连
     *       将当前结点的右节点与新结点相连
     */
    public void rightRotate(){
        //复制出一个与当前结点一样的结点
        Node newNode = new Node(this.data);
        //将新结点的右节点与当前结点的右子节点相连，将当前结点的左子节点的右子结点与新结点的左结点相连
        newNode.setRight(this.right);
        newNode.setLeft(this.left.right);
        //将当前结点的左子节点的值,赋给当前结点，并将当前结点的左节点与左子节点的左子节点相连
        this.data = this.left.data;
        this.left = this.left.left;
        //将当前结点的右节点与新结点相连
        this.right = newNode;
    }
    public void add(Node newNode) {
        if (newNode.data < this.data) {       //小数据往左边放
            if (this.getLeft() == null) {
                this.setLeft(newNode);
            } else {
                this.getLeft().add(newNode);
            }
        } else {            //大数据往右子树走
            if (this.getRight() == null) {
                this.setRight(newNode);
            } else {
                this.getRight().add(newNode);
            }
        }
        if (rightHeight() - leftHeight() > 1) {      //需要左旋
            if (right != null && right.leftHeight() > right.rightHeight()) {   //需要先右旋
                right.rightRotate();
            }
            leftRotate();
        } else if (leftHeight() - rightHeight() > 1) {    //需要右旋
            if (left != null && left.rightHeight() > left.leftHeight()) {    //得先左旋
                left.leftRotate();
            }
            rightRotate();
        }
    }
    /**
     * 按照输入的value，查找拥有相同值的结点
     * @param value   匹配的值
     * @return    找到返回结点，否则返回空
     */
    public Node search(int value){
        if(this.getData() == value){
            return this;
        }else if(value < this.getData()){
            if(this.getLeft() == null){
                return null;
            }else{
                return this.getLeft().search(value);
            }
        }else{
            if(this.getRight() == null){
                return null;
            }else{
                return this.getRight().search(value);
            }
        }
    }
    /**
     * 按照输入的value，查找拥有相同值的结点
     * @param value   匹配的值
     * @return   找到返回结点，否则返回空
     */
    public Node searchParent(int value){
        if((this.getLeft() != null && this.getLeft().getData() == value) || (this.getRight() != null && this.getRight().getData() == value)){
            return this;
        }
        if(this.getLeft()!= null && value< this.getLeft().getData()){
            return this.getLeft().searchParent(value);
        } else if(this.getRight() != null && value > this.getRight().getData()){
            return this.getRight().searchParent(value);
        }else{
            return null;
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.print(this + " ");
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}
class AvlTree{
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
    public void add(Node node){
        if(node == null){
            throw new RuntimeException("结点为空，无法添加");      //手动抛出异常
        }
        if(this.root==null){
            this.root = node;
        }else{
            this.root.add(node);
        }
    }
    public void infixOrder(){
        if(this.root == null){
            System.out.println("空树");
        }else{
            this.root.infixOrder();
        }
    }
    public Node search(int value){
        if(this.root == null){
            throw new RuntimeException("空树");
        }else{
            return this.root.search(value);
        }
    }
    public Node searchParent(int value){
        if(this.root == null){
            throw new RuntimeException("空树");
        }else{
            return this.root.searchParent(value);
        }
    }
    /*
    删除结点有多种情况：
        1，树中只有一个结点：root置空
        2，删除叶子结点：父节点对左或右子节点置空
        3，删除含有左右子树的节点：利用delRightMin方法找到节点右子树中的最小值结点，将其删除，并将其值覆盖到节点中
        4，删除只含有一个子树的结点：父节点对其重新设置为该节点的对应非空子节点
     */
    public void delete(int value){
        if(this.root == null){
            throw new RuntimeException("空树");
        }
        if(this.root.getData() == value){
            Node node = findRightMin(this.root);
            node.setLeft(root.getLeft());
            node.setRight(root.getRight());
            root = node;
            return;
        }
        Node node = this.root.search(value);
        if(node == null){
            throw new RuntimeException("你要删除的结点不存在");
        }
        Node parent = this.root.searchParent(value);

        System.out.println(parent);
        System.out.println(node);
        if(node.getLeft() == null){     //要删除的结点左子树为空
            if(parent.getLeft() == node){      //该结点为父节点的左孩子
                parent.setLeft(node.getRight());
            }else{
                parent.setRight(node.getRight());
            }
        }else if(node.getRight() == null){    //要删除的结点右子树为空
            if(parent.getLeft() == node){      //该结点为父节点的左孩子
                parent.setLeft(node.getLeft());
            }else{
                parent.setRight(node.getLeft());
            }
        }else{         //要删除的结点左右子树都不为空
            Node temp = findRightMin(node);
            temp.setLeft(node.getLeft());
            temp.setRight(node.getRight());
            if(parent.getLeft() == node){      //该结点为父节点的左孩子
                parent.setLeft(temp);
            }else{
                parent.setRight(temp);
            }
        }
    }
    public Node findRightMin(Node node){
        Node temp = node.getRight();      //从要删除的右子树中找到最小的树作为新节点
        Node temp2 = node;
        while(temp.getLeft() != null){
            temp2 = temp;
            temp = temp.getLeft();
        }
        if(temp2.getRight() == temp){
            temp2.setRight(null);
        }else{
            temp2.setLeft(null);    //将找出的新节点从当前位置删除
        }
        return temp;
    }
}
public class AVL_Tree {
    public static void main(String[] args) {
        AvlTree tree = new AvlTree();
        tree.add(new Node(10));
        tree.add(new Node(11));
        tree.add(new Node(7));
        tree.add(new Node(6));
        tree.add(new Node(8));
        tree.add(new Node(9));
        tree.infixOrder();
        System.out.println();
        tree.delete(8);
        System.out.println(tree.getRoot().leftHeight());
        System.out.println(tree.getRoot().rightHeight());
        System.out.println(tree.getRoot().height());
        System.out.println(tree.getRoot());
        tree.infixOrder();
    }
}
